#include "train.h"

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        //int i, j;
        //for (i = 0; i < nums.size() - 1; i++)
        //{
        //    for (j = i + 1; j < nums.size(); j++)
        //    {
        //        if (nums[i] + nums[j] == target)
        //        {
        //            return { i,j };
        //        }
        //    }
        //}
        //return { i,j };

        int n = nums.size();
        vector<int> ind(n); //下标数组
        for (int i = 0; i < n; i++) ind[i] = i;
        sort(ind.begin(), ind.end(), [&](int i, int j)->bool{
                return nums[i] < nums[j];
        }); // 下标数组排序
        int p1 = 0, p2 = n - 1;
        while (nums[ind[p1]] + nums[ind[p2]] != target)
        {
            if (nums[ind[p1]] + nums[ind[p2]] < target) p1++;
            else p2--;
        }
        vector<int> ret(2);
        ret[0] = ind[p1], ret[1] = ind[p2];
        if (ret[0] > ret[1]) swap(ret[0], ret[1]); //从小到大返回下标
        return ret;
    }
};